/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 * 从后往前匹配，如果s[sLength-1] === p[pLength-1]，那么dp[sLength][pLength]的结果取决于前面字符串的匹配结果，即dp[sLength-1][pLength-1]
 */
function isMatch(s, p) {
    const sLength = s.length, pLength = p.length
    const dp = new Array(sLength + 1)
    for (let i = 0; i < sLength + 1; i++) {
        dp[i] = new Array(pLength + 1).fill(false)
    }

    // 双空字符串的匹配
    dp[0][0] = true

    // 个人理解，i和j是从dp的角度出发的
    // 字符串从0开始，考虑到p匹配不全（s匹配结束了，p还有）的情况；j从1开始，是取p的第一个字符
    for (let i = 0; i < sLength + 1; i++) {
        for (let j = 1; j < pLength + 1; j++) {
            // 字符串比较时，减一，从下标0开始，dp的下标00匹配了双空字符串，从1开始
            if (p[j - 1] === '*') {
                dp[i][j] = dp[i][j - 2]     // 未匹配到的情况，不相等s[i-1]!=p[j-2]
                if (match(s, p, i, j - 1)) {   // *号传入第四个参数需要减一，是否匹配星号前的字符
                    dp[i][j] = dp[i - 1][j] || dp[i][j]   // 匹配到多次或0次的情况
                }
            } else {
                if (match(s, p, i, j)) {
                    // 字符串匹配，匹配成功，从false扭转为true
                    dp[i][j] = dp[i - 1][j - 1]
                }
            }
        }
    }
    return dp[sLength][pLength]
}

function match(s, p, i, j) {
    // 空字符串匹配时，考虑数组-1的越界
    if (i === 0) return false
    if (p[j - 1] === '.') return true
    return s[i - 1] === p[j - 1]
}